package simple;

import java.util.*;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/7/31 21:34
 */
public class No219_存在重复元素II {
    public static void main(String[] args) {
        Solution219 solution219 = new Solution219();
        int[] nums = new int[]{1, 2, 3, 1};
        boolean b = solution219.containsNearbyDuplicate(nums, 3);
        System.out.println(b);

    }
}

class Solution219 {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        //哈希映射
        //(值,索引)
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int index = 0; index < nums.length; index++) {
            if (map.get(nums[index]) == null) {
                map.put(nums[index], new ArrayList<>());
            }
            List<Integer> iData = map.get(nums[index]);
            if (iData.size() >= 1) {
                if (index - iData.get(iData.size() - 1) <= k) {
                    return true;
                }
            }
            //索引加入集合
            map.get(nums[index]).add(index);
        }
        return false;
    }
}


    //public boolean containsNearbyDuplicate(int[] nums, int k) {
    //    //暴力法
    //    List<Integer> list = new ArrayList<>();
    //    for (int i = 0; i < nums.length; i++) {
    //        if (i > k) {
    //            list.remove(0);
    //        }
    //        if (list.contains(nums[i])) {
    //            return true;
    //        }
    //        list.add(nums[i]);
    //    }
    //    return false;
    //
    //}